package com.rr.middle;

import java.math.BigDecimal;

/**
 * @author zhuangcanrun
 * @Date 2022/01/10/12:52
 * @description
 **/

/*
 * https://leetcode-cn.com/problems/additive-number/
 * */
public class IsAdditiveNumber {
    public boolean isAdditiveNumber(String num) {
        int[] intArray = getIntArray(num);
        int length = intArray.length;
        for (int i = 0; i < length - 2; i++) {
            BigDecimal firstNum = getNumFromArray(0, i, intArray);
            for (int j = 0; i + 1 + j < length - 1; j++) {
                BigDecimal secondNum = getNumFromArray(i + 1, i + 1 + j, intArray);
                if (isOk(firstNum, secondNum, i + 1 + j + 1,intArray,length)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isOk(BigDecimal firstNum, BigDecimal secondNum, int start, int[] intArray, int end) {
        for (int i = 0; start + i < end; i++) {
            BigDecimal thirdNum = getNumFromArray(start, start + i, intArray);
            if (firstNum.add(secondNum).equals(thirdNum)) {
                if (start + i == end - 1) {
                    return true;
                }
                firstNum = secondNum;
                secondNum = thirdNum;
                if (isOk(firstNum, secondNum, start + i + 1, intArray, end)) {
                    return true;
                }
            }
        }
        return false;
    }

    private int[] getIntArray(String num) {
        int length = num.length();
        int[] numArray = new int[length];
        for (int i = 0; i < length; i++) {
            numArray[i] = num.charAt(i) - 48;
        }
        return numArray;
    }

    private BigDecimal getNumFromArray(int start, int end, int[] numArray) {
        BigDecimal result = new BigDecimal(0);
        if (numArray[start] == 0 && end > start) {
            return new BigDecimal(Integer.MAX_VALUE);
        }
        for (; start <= end; start++) {
            result = result.multiply(new BigDecimal(10)).add(new BigDecimal(numArray[start]));
        }
        return result;
    }

    public static void main(String[] args) {
        IsAdditiveNumber isAdditiveNumber = new IsAdditiveNumber();
        System.out.println(isAdditiveNumber.isAdditiveNumber("10101"));
    }
}
